class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto& e : nums)
        {
            sum += e;
        }
        if(sum % 2 == 1) // 如果是奇数直接返回false
            return false;
        
        int target = sum / 2, n = nums.size();
        vector<bool> dp(target + 1, false); // 滚动数组优化
        dp[0] = true;
 
        for(int i = 1; i <= n; ++i)
        {
            for(int j = target; nums[i - 1] <= j; --j)
            {
                dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        }
        return dp[target];
    }
};